package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC650 {


    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }


    static class Solution {
        /*
         * @param root: the root of binary tree
         * @return: collect and remove all leaves
         */
        public List<List<Integer>> findLeaves(TreeNode root) {
            //构造图  针对某个节点：from为自己，to为父节点
            Queue<TreeNode> q = new LinkedList<>();
            if(root ==null) return new ArrayList<>();
            q.add(root);
            Map<TreeNode,Gnode> g = new HashMap<>(); //图
            g.put(root,new Gnode(root));
            while (!q.isEmpty()){
                int size = q.size();
                for (int i = 0; i <size ; i++) {
                    TreeNode to = q.poll();
                    if(!g.containsKey(to)){
                        g.put(to,new Gnode(to));
                    }
                    if(to.left!=null){
                        TreeNode from = to.left;
                        q.add(from);

                        g.put(from,new Gnode(from));
                        g.get(from).nexts.add(g.get(to));
                        g.get(to).nexts.add(g.get(from));
                        g.get(to).in++;
                    }

                    if(to.right!=null){
                        TreeNode from = to.right;
                        q.add(from);
                        g.put(from,new Gnode(from));
                        g.get(from).nexts.add(g.get(to));
                        g.get(to).nexts.add(g.get(from));
                        g.get(to).in++;

                    }
                }
            }

            //宽度优先BFS
            Queue<Gnode> q0 = new LinkedList<>();
            for(TreeNode node: g.keySet()){
                if(g.get(node).in==0){
                    q0.add(g.get(node));
                }
            }
            List<List<Integer>>  ans = new ArrayList<>();

            while (!q0.isEmpty()){
                int size = q0.size();
                List<Integer> t = new ArrayList<>();
                for (int i = 0; i <size ; i++) {
                    Gnode pop = q0.poll();
                    t.add(pop.data.val);
                    for (Gnode next : pop.nexts) {
                        if(--next.in ==0){
                            q0.add(next);
                        }
                    }
                }

                ans.add(t);
            }
            return ans;
        }

        static class Gnode { //图的节点定义
            TreeNode data;
            int in;
            List<Gnode> nexts;

            public Gnode(TreeNode d) {
                data = d;
                nexts = new ArrayList<>();
            }
        }

    }

    public static void main(String[] args) {

    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有195条未读消息，请及时查看
650 · 二叉树叶子顺序遍历
算法
中等
通过率
68%

题目
题解28
笔记
讨论99+
排名
记录
描述
给定一个二叉树，像这样收集树节点：收集并移除所有叶子，重复，直到树为空。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例1
输入： {1,2,3,4,5}
输出： [[4, 5, 3], [2], [1]].
解释：

    1
   / \
  2   3
 / \
4   5
样例2
输入： {1,2,3,4}
输出： [[4, 3], [2], [1]].
解释：

    1
   / \
  2   3
 /
4
标签
企业
领英
相关题目

97
二叉树的最大深度
简单

155
二叉树的最小深度
简单
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
30 分 00 秒
12345678910111213141516171819202122
    }
}
控制台
历史提交

 */

/*
package com.ds.practice.exec2022and2023.ms2022.ms.before2023317.day218;

import java.util.*;

public class LC650 {

    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }


        //构造二叉搜索树
        public TreeNode createTree(int[] arr) {
            TreeNode root = new TreeNode(arr[0]);
            for (int i = 1; i < arr.length; i++) {
                TreeNode parent = root;
                TreeNode tmp = root;

                while (tmp != null) {
                    parent = tmp;
                    if (tmp.val > arr[i]) {
                        tmp = tmp.left;
                    } else if (tmp.val < arr[i]) {
                        tmp = tmp.right;
                    } else {
                        tmp.val = arr[i];
                        continue;
                    }
                }

                if (parent.val > arr[i]) {
                    parent.left = new TreeNode(arr[i]);
                } else {
                    parent.right = new TreeNode(arr[i]);
                }
            }

            return root;
        }




    public List<List<Integer>> findLeaves(TreeNode root) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null) return ans;
        TreeNode node  = root;
        Queue<TreeNode> queue = new LinkedList<>();
        Map<TreeNode,TPNode> map = new HashMap<>();
        queue.offer(node);

        while(!queue.isEmpty()){
            TreeNode to = queue.poll();
            if(!map.containsKey(to)) {
                map.put(to,new TPNode(to));
            }
            TPNode toNode = map.get(to);
            if(to.left!=null){
                TreeNode from1 = to.left;
                if(!map.containsKey(from1)){
                    map.put(from1,new TPNode(from1));
                }
                TPNode f1 = map.get(from1);
                f1.nexts.add(toNode);
                toNode.in++;
                queue.offer(to.left);
            }
            if(to.right!=null){
                TreeNode from2 = to.right;
                if(!map.containsKey(from2)){
                    map.put(from2,new TPNode(from2));
                }

                TPNode f2 = map.get(from2);
                f2.nexts.add(toNode);
                toNode.in++;
                queue.offer(to.right);
            }
        }


        Queue<TPNode> q0 =new LinkedList<>();
        for(TPNode cur:map.values()){
            if(cur.in==0){
                q0.add(cur);
            }
        }
        List<Integer> per = new ArrayList<>();
        int size = q0.size();

        while (!q0.isEmpty()){
            TPNode pop = q0.poll();
            per.add(pop.val.val);
            for(TPNode next: pop.nexts){
                if(--next.in ==0){
                    q0.add(next);
                }
            }
            size--;
            if(size ==0){
                List<Integer> tmp = new ArrayList<>();
                for (Integer item : per) {
                    tmp.add(item);
                }
                ans.add(tmp);
                per.clear();
                size = q0.size();
            }
        }
        return ans;
    }

    static class TPNode{
        TreeNode val;
        int in;
        List<TPNode> nexts;
        public TPNode(TreeNode val){
            this.val = val;
            nexts = new ArrayList<>();
        }
    }



        public static void main(String[] args) {
//            int[] arr = {10, 5, 4, 6, 14, 13, 15};
            LC650 obj = new LC650();
//            TreeNode tree =
            TreeNode tree = new TreeNode(1);
            tree.left = new TreeNode(2);
            tree.right = new TreeNode(3);
            tree.left.left= new TreeNode(4);
            tree.left.right= new TreeNode(5);
            TreeNodeShow.show(tree);
            System.out.println(obj.findLeaves(tree)); //答案是 [[4, 5, 3], [2], [1]]
        }


        //打印二叉树的类
        static class TreeNodeShow {

            // 用于获得树的层数
            private static int getTreeDepth(TreeNode root) {
                return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
            }

            private static void writeArray(TreeNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
                // 保证输入的树不为空
                if (currNode == null) return;
                // 先将当前节点保存到二维数组中
                res[rowIndex][columnIndex] = String.valueOf(currNode.val);

                // 计算当前位于树的第几层
                int currLevel = ((rowIndex + 1) / 2);
                // 若到了最后一层，则返回
                if (currLevel == treeDepth) return;
                // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
                int gap = treeDepth - currLevel - 1;

                // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
                if (currNode.left != null) {
                    res[rowIndex + 1][columnIndex - gap] = "/";
                    writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
                }

                // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
                if (currNode.right != null) {
                    res[rowIndex + 1][columnIndex + gap] = "\\";
                    writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
                }
            }


            public static void show(TreeNode root) {
                if (root == null) {
                    System.out.println("EMPTY!");
                    return;
                }
                // 得到树的深度
                int treeDepth = getTreeDepth(root);

                // 最后一行的宽度为2的（n - 1）次方乘3，再加1
                // 作为整个二维数组的宽度
                int arrayHeight = treeDepth * 2 - 1;
                int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
                // 用一个字符串数组来存储每个位置应显示的元素
                String[][] res = new String[arrayHeight][arrayWidth];
                // 对数组进行初始化，默认为一个空格
                for (int i = 0; i < arrayHeight; i++) {
                    for (int j = 0; j < arrayWidth; j++) {
                        res[i][j] = " ";
                    }
                }

                // 从根节点开始，递归处理整个树
                // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
                writeArray(root, 0, arrayWidth / 2, res, treeDepth);

                // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
                for (String[] line : res) {
                    StringBuilder sb = new StringBuilder();
                    for (int i = 0; i < line.length; i++) {
                        sb.append(line[i]);
                        if (line[i].length() > 1 && i <= line.length - 1) {
                            i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                        }
                    }
                    System.out.println(sb.toString());
                }
            }
        }




}

 */
